package org.c41.util.collection;

import java.util.Iterator;

public class LinkedList<E> implements Iterable<E>{

	private Node<E> first;
	private Node<E> last;
	private int size;

	public LinkedList(){
	}

	public Node<E> addFirst(E e){
		Node<E> nnode = new Node<>(this,e);
		if(size!=0){
			nnode.after = first;
			first.before=nnode;
			first=nnode;
		}
		else{
			first=last=nnode;
		}
		size++;
		return nnode;
	}

	public Node<E> addLast(E e){
		Node<E> nnode = new Node<>(this,e);
		if(size!=0){
			nnode.before = last;
			last.after=nnode;
			last=nnode;
		}
		else{
			first=last=nnode;
		}
		size++;
		return nnode;
	}

	public E removeFirst(){
		if(first==null){
			return null;
		}
		E e = first.e;
		first.close();
		if(first==last){
			first=last = null;
		}
		else{
			first.after.before = null;
			first = first.after;
		}
		size--;
		return e;
	}

	public E removeLast(){
		if(last==null){
			return null;
		}
		E e = last.e;
		last.close();
		if(first==last){
			first=last = null;
		}
		else{
			last.before.after = null;
			last = last.before;
		}
		size--;
		return e;
	}
	
	public E getFirst(){
		return first.e;
	}

	public Node<E> getFirstNode(){
		return first;
	}

	public E getLast(){
		return last.e;
	}

	public Node<E> getLastNode(){
		return last;
	}

	public int size(){
		return this.size;
	}
	
	private Node<E> addBefore(Node<E> node, E e){
		if(node==first){
			return addFirst(e);
		}
		Node<E> _2 = new Node<>(this,e);
		Node<E> _1 = node.before;
		
		_1.after=_2;
		_2.before=_1;
		_2.after=node;
		node.before=_2;
		size++;
		return _2;
	}
	
	private Node<E> addAfter(Node<E> node, E e){
		if(node==last){
			return addLast(e);
		}
		Node<E> _2 = new Node<>(this,e);
		Node<E> _3 = node.after;
		
		_3.before=_2;
		_2.after=_3;
		_2.before=node;
		node.after=_2;
		size++;
		return _2;
	}
	
	private void remove(Node<E> node){
		if(node==first){
			removeFirst();
			return;
		}
		if(node==last){
			removeLast();
			return;
		}
		Node<E> _1 = node.before;
		Node<E> _2 = node.after;
		_1.after=_2;
		_2.before=_1;
		node.close();
		size--;
	}
	
	@Override
	public Iterator<E> iterator() {
		return new MyIt();
	}

	public Node<E> getNode(int index){
		if(index<=size/2){
			return first.getNodeAfter(index);
		}
		else{
			return last.getNodeBefore(size-index-1);
		}
	}
	
	public E get(int index){
		return getNode(index).e;
	}
	
	private class MyIt implements Iterator<E>{

		private Node<E> node = first;
		
		@Override
		public boolean hasNext() {
			return node!=null;
		}

		@Override
		public E next() {
			E e = node.e;
			node=node.next();
			return e;
		}

		@Override
		public void remove() {
			Node<E> n = node;
			node = node.after;
			n.remove();
		}
		
	}
	
	public static class Node<E>{

		private LinkedList<E> belong;
		private E e;
		private Node<E> before;
		private Node<E> after;

		private Node(LinkedList<E>belong, E e){
			this.e=e;
			this.belong=belong;
		}

		public E element(){
			return e;
		}

		public Node<E> next(){
			return after;
		}
		
		public Node<E> before(){
			return before;
		}
		
		public Node<E> addBefore(E e){
			return belong.addBefore(this, e);
		}
		
		public Node<E> addAfter(E e){
			return belong.addAfter(this, e); 
		}
		
		private void close(){
			this.belong=null;
			this.before=null;
			this.after=null;
		}
		
		public boolean isFirstNode(){
			return belong!=null&&before==null;
		}
		
		public boolean isLastNode(){
			return belong!=null&&after==null;
		}
		
		public void remove(){
			belong.remove(this);
		}
		
		public Node<E> getNodeAfter(int index){
			Node<E> node = this;
			for(int i=0;i<index;i++){
				node = node.next();
			}
			return node;
		}
		
		public E getAfter(int index){
			return getNodeAfter(index).e;
		}
		
		public Node<E> getNodeBefore(int index){
			Node<E> node = this;
			for(int i=0;i<index;i++){
				node = node.before();
			}
			return node;
		}
		
		public E getBefore(int index){
			return getNodeBefore(index).e;
		}
		
	}
	
}
